A programmable digital computer provides a readily adaptable environment to simulate physical systems such as a communication network or a multi-layer protocol. A system model, once described, can be analyzed extensively and then the model may be modified to study the effects of perturbations. Although there are numerous methods of simulation, they depart primarily in their details, not in their general characteristics. Most general purpose simulators exhibit the following essential characteristics: (1) the model, once activated from an initial condition, is represented by a series of events corresponding to changes in states of the model and, oftentimes, these changes are associated with particular instants of time in a simulated time environment; and (2) simulated time must not be affected by the time required to compute the events or state changes.
However, in order to make simulations tractable for complex systems, oftentimes it is necessary that parallel processing be utilized. With parallel processing, system computations are subdivided into tasks that are suitable for execution in parallel. The tasks are then distributed among a plurality of synchronized processors for autonomous execution. An inherent problem in the parallel approach, however, is the difficulty in ensuring that the computations, which are distributed among the processors for autonomous execution, are properly synchronized or aligned. As a simple example, it is supposed that two processors are executing in parallel and the first processor requires the results from the second processor. Then, the simulation must be arranged so that the second processor communicates its results to the first processor before the second processor may continue its computations; this is particularly important if the second processor completes its execution before the execution of the first processor is completed.
One recently disclosed approach to effecting state alignment was described in U.S. Pat. No. 4,833,638 issued May 23, 1989 to Vollaro. As disclosed in this patent, the processing states allocated to a plurality of autonomous processors comprising a multiple processor system are aligned by providing each processor with means for inhibiting a global reference generator within one unit of real time. The reference generator is restarted only after all task processing is completed in the order required by the sequence of changing states. To achieve maximum execution efficiency, the inevitable periods of long delay between scheduled states are detected and the system is advanced to the earliest, next scheduled state in a few, predetermined units of real time.
With respect to the specific processor computations during each of the processing states, the results have been conventionally stored in a single memory which is common to or shared among the several processors via a multiple access memory bus interconnecting the memory with the processors. Traditional methods for accessing and then storing computational data into the single memory possess inherent deficiencies. Two prime areas of difficulty are excessive loading of the memory bus and high overhead manifested by extra, unproductive processor cycles. Both of these factors may lead to unsuccessful access to the memory because of busy or blocking conditions exhibited by either the bus or the memory, or both simultaneously. The main cause of these difficulties is the constraint induced by the architectural arrangement, namely, the need to request and then acquire two shared resources (bus and memory) in series with some probability that access to each resource may fail due to blocking. In the case of a failure because of a busy condition, the entire access process must be continually repeated until access succeeds. The failure rate is exacerbated whenever the demand for memory access increases.
A so-called conflict, that is, a simultaneous update of the same memory location by two or more processors at the same instant of time, is another situation that is difficult to handle in shared memory systems. Multiple processors sharing the same data are called overlapping processes and the prevention of other processors from accessing shared data while one processor is doing so is called mutual exclusion. Several conventional techniques for implementing mutual exclusion, such as semaphores and test and set instructions, are detailed in the text entitled An Introduction to Operating Systems, by H. M. Ditel, Addison-Wesley, 1983, Chapter 4. These techniques also suffer from similar performance and overhead problems discussed above and, moreover, are extremely error-prone when handled by user-written software.
Finally, standard shared memory systems employ a destructive write process. Thus, when a memory location is modified, the contents of that location are replaced with the modified data and the original data is destroyed. This process, when combined with traditional conflict resolution techniques, basically obliterates the data history of each memory location, thereby either limiting the processor to using only the single data value presently stored in the memory location at the end of each computational phase or requiring elaborate recomputation procedures to reconstruct overwritten data.
There has been no teaching or suggestion in the art to synchronize time alignment of processing states with concurrency of data propagation.